function [settings,SEARCH] = update_search(settings,SEARCH,currErr)
% update search progress
if ~settings.search_for_k, SEARCH.in_progress = false; return; end

SEARCH.E(settings.k==SEARCH.x) = currErr;

% any other unfinished values of k?
unfinished = find(SEARCH.E==-1);
if ~isempty(unfinished), settings.k = SEARCH.x(unfinished(1)); return; end

% check where is minimum
[MINIMAL_ERROR,minE_id] = min(SEARCH.E);

if SEARCH.step == 1 || MINIMAL_ERROR == 0
    % smallest possible step or error => terminate search
    SEARCH.in_progress = false;
    SEARCH.optimal_k = SEARCH.x(SEARCH.E==MINIMAL_ERROR);
    SEARCH.optimal_k = SEARCH.optimal_k(1);
    return;
end


if minE_id == 1
    % smallest k is the best => reduce step
    SEARCH.step = floor(SEARCH.step/2);
    SEARCH = add_gridpoints(SEARCH,SEARCH.x(1)+SEARCH.step*[-1 1]);
elseif minE_id == length(SEARCH.x)
    % largest k is the best
    if SEARCH.x(end) + SEARCH.step <= settings.max_dim && (min(abs(SEARCH.x(end) + SEARCH.step-SEARCH.x))>SEARCH.step/2)
        % continue to the right
        SEARCH = add_gridpoints(SEARCH,SEARCH.x(end) + SEARCH.step);
    else
        % hitting the full dimensionality
        if (MINIMAL_ERROR/SEARCH.E(end-1) >= 1 - settings.Eoob_tolerance) ... % desired tolerance fulfilled
            || SEARCH.E(end-1)-MINIMAL_ERROR < 5e-3 ... % maximal precision in terms of error set to 0.5%
            || SEARCH.step<SEARCH.x(minE_id)*0.05 ... % step is smaller than 5% of the optimal value of k
            % stopping criterion met
            SEARCH.in_progress = false;
            SEARCH.optimal_k = SEARCH.x(SEARCH.E==MINIMAL_ERROR);
            SEARCH.optimal_k = SEARCH.optimal_k(1);
            return;
        else
            % reduce step
            SEARCH.step = floor(SEARCH.step/2);
            if SEARCH.x(end) + SEARCH.step <= settings.max_dim
                SEARCH = add_gridpoints(SEARCH,SEARCH.x(end)+SEARCH.step*[-1 1]);
            else
                SEARCH = add_gridpoints(SEARCH,SEARCH.x(end)-SEARCH.step);
            end;
        end
    end
elseif (minE_id == length(SEARCH.x)-1) ... % if lowest is the last but one
        && (settings.k + SEARCH.step <= settings.max_dim) ... % one more step to the right is still valid (less than d)
        && (min(abs(settings.k + SEARCH.step-SEARCH.x))>SEARCH.step/2) ... % one more step to the right is not too close to any other point
        && ~(SEARCH.E(end)>SEARCH.E(end-1) && SEARCH.E(end)>SEARCH.E(end-2)) % the last point is not worse than the two previous ones
    % robustness ensurance, try one more step to the right
    SEARCH = add_gridpoints(SEARCH,settings.k + SEARCH.step);
else
    % best k is not at the edge of the grid (and robustness is resolved)
    err_around = mean(SEARCH.E(minE_id+[-1 1]));
    if (MINIMAL_ERROR/err_around >= 1 - settings.Eoob_tolerance) ... % desired tolerance fulfilled
        || err_around-MINIMAL_ERROR < 5e-3 ... % maximal precision in terms of error set to 0.5%
        || SEARCH.step<SEARCH.x(minE_id)*0.05 ... % step is smaller than 5% of the optimal value of k
        % stopping criterion met
        SEARCH.in_progress = false;
        SEARCH.optimal_k = SEARCH.x(SEARCH.E==MINIMAL_ERROR);
        SEARCH.optimal_k = SEARCH.optimal_k(1);
        return;
    else
        % reduce step
        SEARCH.step = floor(SEARCH.step/2);
        SEARCH = add_gridpoints(SEARCH,SEARCH.x(minE_id)+SEARCH.step*[-1 1]);
    end
end

unfinished = find(SEARCH.E==-1);
settings.k = SEARCH.x(unfinished(1));
return;
